The ultimate goal of secure electronic voting is to replace physical voting booths. Achieving this goal requires work both on improving the efficiency of current protocols and understanding the security properties that these physical devices can provide.
Recently, it is observed in an article by J. C. Benaloh et al, entitled "Receipt-free Secret-ballot Election," in STOC 94, pp. 544-553 (1994), that unlike physical voting protocols, nearly all electronic voting protocols give the voters a receipt by which they can prove how they voted. Such receipts provide a ready means by which voters can sell their votes or by which another party can coerce a voter to vote in a certain way.
Benaloh and Tuninstra give the first receipt-free protocol for electronic voting. In their scheme a trusted center generates for each voter a pair of ballots consisting of a "yes" vote and a "no" vote in random order. Using a trusted beacon and a physical voting booth the center proves to the public that the ballot indeed includes a well-formed (yes/no) or (no/yes) pair and at the same time proves to the verifier which pair it is. The physical apparatus ensures that by the time the verifier is able to communicate with an outsider, the verifier can forge a proof that the ballot is (yes/no) and also forge a proof that it is (no/yes). Thus, such a proof ceases to provide either proof as a receipt.
Independently, Nieni and Renvall tried to solve this problem in an article by Niemi et al, entitled "How to prevent buying of votes in computer elections" in ASIACRYPT '94, pp. 141-148 (1994). They also use a physical voting booth where a voter performs multiparty computation with all the centers.
Both the Benaloh-Tuinstra and the Niemi-Renivall protocols illustrate that receipt-free secure voting is possible. However, their physical requirements are fairly cumbersome, and are not unlike those faced by participants in physical elections. An important open question is precisely what physical requirements are necessary for achieving receipt-free secure voting.
In accordance with the teachings of the present invention, a secure receipt-free voting scheme is described with a more practical physical requirement, that is the existence of a physically secure untappable private channel.